计算机基础 - 0 操作系统

发表于 | 分类于 | | 阅读次数:
字数统计: 4k | 阅读时长 ≈ 13

题目合集

进程管理

一、进程和线程的区别

  • 按照操作系统的概念：
    • 进程为一个独立执行单元（是系统进行资源调度和分配的基本单位），在PC或者移动端是程序和应用的执行。
    • 线程为CPU调度的最小单元，是有限资源。一个进程可以包含多个线程。
  • 异：
    • 组成：唯一标示为进程控制块PCB + 资源、线程控制块TCB(栈)
    • 资源：进程间的资源是分隔独立的，内存映射表不同，占用物理内存地址是分隔的；线程的资源是共享所在进程的。
    • 切换：线程切换了TCB（栈结构），进程还包括切换资源，即切换内存映射表
  • 同：
    • 运行状态：就绪、运行、阻塞。运行时受阻如需要资源之后会变为阻塞，获取资源后变为就绪，再次运行。
  • iOS中的进程和线程
    • 进程：一个iOS程序运行后，该运行的程序就是进程。默认会开启1条线程，称为“主线程”
    • 线程：从用途上来说，线程分为主线程和子线程，主线程的作用是「显示刷新页面；处理UI事件」，而子线程的作用则是「执行耗时任务，比如网络请求、I/O 操作等」。如果在主线程中执行耗时操作那么就会导致程序无法及时地响应。因此耗时操作必须放在子线程中执行。
    • 多线程的实现：pthread，NSthread，GCD，NSOperation。

二、进程通信

（一）广义的进程间通信

本地进程间通信的方式有很多，可以总结为下面四类：

  • 消息传递（管道、FIFO、消息队列）
  • 同步（互斥量、条件变量、读写锁、文件和写记录锁、信号量）
  • 共享内存（匿名的和具名的）
  • 远程过程调用（Solaris门和Sun RPC）

（二）狭义的进程间通信

1、共享存储器系统

A、共享数据结构：信息交换的格式、类型一定；进程通信由程序员完成，效率低；

B、共享存储区：进程可随时向系统申请一块存储区，并指定该分区的关键字，用于进程通信。

2、消息传递系统

A、直接通信方式 Send(Receiver,message);Receive(Sender,message);

B、间接通信方式：1、信箱的创建、撤消； 2、消息的发送和接受；Send(mailbox,message);

3、管道通信

管道：用于连接一个读进程和一个写进程，以实现它们之间通信的共享文件，又称为Pipe文件。

功能：Command1进程以字符流的形式向管道发送大量的数据，Command2进程则从管道接收数据。两进程实现单向、同步、互斥运行。单向：Command1只能发送；同步：管道满时，Command1等待；互斥：同一时刻，只能有一个进程对管道操作；

4、消息队列（message queue）：消息队列是由消息组成的链表，存放在内核中 并由消息队列标识符标识。消息队列克服了信号传递信息少，管道只能承载无格式字节流以及缓冲区大小受限等缺点。

5、套接字（socket）：套接口也是一种进程间的通信机制，与其他通信机制不同的是它可以用于不同的主机间的进程通信。通过”套接字”向网络发出请求或者应答网络请求。

三、死锁

在两个或多个并发进程中，如果每个进程持有某种资源而又都等待别的进程释放它或它们现在保持着的资源，在未改变这种状态之前都不能向前推进，称这一组进程产生了死锁。

✨产生条件：互斥、占有等待、非剥夺和循环等待。

  • 互斥条件 ：一个资源一次只能被一个进程使用
  • 请求保持条件 ：一个进程因请求资源而阻塞时，对已经获得资源保持不放
  • 不可抢占条件 ：进程已获得的资源在未使用完之前不能强行剥夺
  • 循环等待条件 ：若干进程之间形成一种头尾相接的循环等待资源的关系

✨死锁处理：

破坏产生死锁的4个必要条件中的一个或者多个

  • 预防死锁：预先静态分配法（破坏不可剥夺条件）、资源有序分配法（将资源分类按顺序排列，保证不形成环路）。
  • 避免死锁：银行家算法（对每个资源请求进行检测，确保安全。需要很大的系统开销）。
  • 检测死锁：资源分配图简化，非孤立点的进程处于死锁状态。
  • 解除死锁：资源剥夺法、撤销进程法。

四、CPU调度算法 （在就绪序列中怎么挑选进程让CPU执行）

先来先服务调度算法FCFS：按作业或者进程到达的先后顺序依次调度；（平均周转时间可能会很长 ）

短作业优先调度算法SJF：算法从就绪队列中选择估计时间最短的作业进行处理，直到得出结果或者无法继续执行（周转时间短，但是响应时间长 ）

时间片轮转调度RR：按到达的先后对进程放入队列中，然后给队首进程分配CPU时间片，时间片用完之后计时器发出中断，暂停当前进程并将其放到队列尾部，循环 ;（响应时间可以得到保证）

多级反馈队列调度算法：目前公认较好的调度算法；设置多个就绪队列并为每个队列设置不同的优先级，第一个队列优先级最高，其余依次递减。(堆实现优先队列)

五、锁

多线程编程中需要使用的锁。锁要解决的是线程之间争取资源的问题，这个问题大概有下面几个角度：

  • 资源是否是独占（独占锁 - 共享锁）
  • 抢占不到资源怎么办（互斥锁 - 自旋锁）
  • 自己能不能重复抢（重入锁 - 不可重入锁）
  • 竞争读的情况比较多，读可不可以不加锁（读写锁）

内存管理

六、堆栈

栈是用于存放本地变量，内部临时变量以及有关上下文的内存区域。系统操作，不需要程序员手动干预。

栈是一块连续的内存区域，栈顶的地址和栈的最大容量是系统预先规定好的。eg.递归过深，超过，stackoverflow

七、缓存算法

LRU（least recently used）最近最久未使用

页面置换算法——插入、访问、淘汰。

1、哈希+双向链表：

现在哈希表中查询是否存在该数据，根绝索引找到数据存储的位置，查询时间变为O(1)。

先查询链表中是否有该分页，没有的话查看cache是否满，未满直接放在头尾；满了则删除尾部，再将其放在头部。

存在该分页，则先移除原本的node，将其放在头部。

2、哈希表+数组 ：

哈希表存储数据项对应的位置+频次，被访问后频次+1。插入和访问为O(1)

淘汰的时候在表中找到最少访问的，在数组中删除，再放入新的内容，淘汰为O(n)。

操作系统五个基本功能

1、存储管理：内存分配、内存保护、地址映射、内存扩充
2、处理机管理：进程控制、进程同步、进程通信、进程调度
3、设备管理：缓冲管理、设备分配、设备处理、设备独立性和虚拟设备
4、文件管理：外存管理、目录管理、文件操作
5、用户接口：命令接口、程序接口、图形接口

第2部分 进程管理

第1章 进程与线程

1.1 进程

进程（Process)：一个具有一定独立功能的可并发执行的程序，在一个数据集合上的运行过程。用来记录进程信息的数据结构

进程控制块PCB：用以记录与进程相关信息的主存区，是进程存在的唯一标志（管理进程的核心，包含了PID等进程的所有关键信息）用链接指针链成队列；

进程的三种基本状态（多线程时也是这些状态）

  • ​ 运行状态(Running)
  • ​ 就绪状态(Ready)
  • ​ 阻塞状态(Block)

队列：就绪队列、等待（阻塞）队列。

  • 处于就绪状态的进程，在调度程序为之分配了处理机之后便开始执行， 就绪 -> 执行
  • 正在执行的进程如果因为分配他的时间片已经用完，而被剥夺处理剂， 执行 -> 就绪
  • 如果因为某种原因致使当前的进程执行受阻，使之不能执行。 执行 -> 阻塞

1.2 线程

线程(Thread)，是进程中的一个实体，是能被系统独立调度和分派的基本单位。引入线程，是为了减小程序在并发执行时所付出的时空开销，提高操作系统的并发性能。

线程最直接的理解就是“轻量级进程”。

2.3 进程和线程的对比

进程是系统进行资源调度和分配的基本单位；线程是CPU调度的基本单位。

进程 = 资源 （包括寄存器值，PCB，内存映射表）+ TCB（栈结构）
线程 = TCB（栈结构）

线程 的资源是共享的
进程 间的资源是分隔独立的，内存映射表不同，占用物理内存地址是分隔的

线程 的切换只是切换PC，切换了TCB（栈结构）
进程 的切换不仅要切换PC，还包括切换资源，即切换内存映射表

第2章 进程的同步与通信

2.1 进程同步

进程之间存在两种基本关系：竞争关系和协作关系。

同步的解决方案：管程，信号量。

信号量

即利用PV操作来对信号量进行处理。当它的值大于0时，表示当前可用资源的数量；

当它的值小于0时，其绝对值表示等待使用该资源的进程个数。信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它通常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。因此，主要作为进程间以及同一进程内不同线程之间的同步手段。

2.2 进程的数据通信

1、共享存储器系统

A、共享数据结构：

信息交换的格式、类型一定；

进程通信由程序员完成，效率低；

B、共享存储区：

进程可随时向系统申请一块存储区，

并指定该分区的关键字，用于进程通信。

2、消息传递系统

A、直接通信方式 Send(Receiver,message);Receive(Sender,message);

B、间接通信方式：1、信箱的创建、撤消； 2、消息的发送和接受；

Send(mailbox,message); Receive(mailbox,message);

3、管道通信(Pipe Communication)

管道：用于连接一个读进程和一个写进程，以实现它们之间通信的共享文件，又称为Pipe文件。

功能：Command1进程以字符流的形式向管道发送大量的数据，Command2进程则从管道接收数据。两进程实现单向、同步、互斥运行。

​ 单向：Command1只能发送；

​ 同步：管道满时，Command1等待；

​ 互斥：同一时刻，只能有一个进程对管道操作；

（4）消息队列（message queue）：消息队列是由消息组成的链表，存放在内核中 并由消息队列标识符标识。消息队列克服了信号传递信息少，管道只能承载无格式字节流以及缓冲区大小受限等缺点。

（5）套接字（socket）：套接口也是一种进程间的通信机制，与其他通信机制不同的是它可以用于不同的主机间的进程通信。通过”套接字”向网络发出请求或者应答网络请求。

2.3 几种线程间的通信机制

1、锁机制

1.1 互斥锁：提供了以排它方式阻止数据结构被并发修改的方法。

1.2 读写锁：允许多个线程同时读共享数据，而对写操作互斥。

1.3 条件变量：可以以原子的方式阻塞进程，直到某个特定条件为真为止。对条件测试是在互斥锁的保护下进行的。条件变量始终与互斥锁一起使用。

2、信号量机制：包括无名线程信号量与有名线程信号量

3、信号机制：类似于进程间的信号处理。

###

第4章 调度与死锁

CPU调度算法 （在就绪序列中怎么挑选进程让CPU执行）

先了解两个概念：

  • 周转时间： 从开始申请执行任务，到执行任务完成
  • 响应时间： 从开始申请执行任务到开始执行任务

先来先服务调度算法FCFS：按作业或者进程到达的先后顺序依次调度；（平均周转时间可能会很长 ）

短作业优先调度算法SJF：算法从就绪队列中选择估计时间最短的作业进行处理，直到得出结果或者无法继续执行（周转时间短，但是响应时间长 ）

高相应比算法HRN：响应比=(等待时间+要求服务时间)/要求服务时间；

时间片轮转调度RR：按到达的先后对进程放入队列中，然后给队首进程分配CPU时间片，时间片用完之后计时器发出中断，暂停当前进程并将其放到队列尾部，循环 ;（响应时间可以得到保证）

多级反馈队列调度算法：目前公认较好的调度算法；设置多个就绪队列并为每个队列设置不同的优先级，第一个队列优先级最高，其余依次递减。

✨死锁

　　在两个或多个并发进程中，如果每个进程持有某种资源而又都等待别的进程释放它或它们现在保持着的资源，在未改变这种状态之前都不能向前推进，称这一组进程产生了死锁。通俗地讲，就是两个或多个进程被无限期地阻塞、相互等待的一种状态。

✨产生条件：互斥、占有等待、非剥夺和循环等待。

  • 互斥条件 ：一个资源一次只能被一个进程使用

  • 请求保持条件 ：一个进程因请求资源而阻塞时，对已经获得资源保持不放

  • 不可抢占条件 ：进程已获得的资源在未使用完之前不能强行剥夺

  • 循环等待条件 ：若干进程之间形成一种头尾相接的循环等待资源的关系

✨死锁处理：

破坏产生死锁的4个必要条件中的一个或者多个

  • 预防死锁：预先静态分配法（破坏不可剥夺条件）、资源有序分配法（将资源分类按顺序排列，保证不形成环路）。
  • 避免死锁：银行家算法（对每个资源请求进行检测，确保安全。需要很大的系统开销）。
  • 检测死锁：资源分配图简化，非孤立点的进程处于死锁状态。
  • 解除死锁：资源剥夺法、撤销进程法。